<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>正则表达式匹配算法解析</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', 'Noto Serif SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            color: #333;
            line-height: 1.6;
            background-color: #f8f9fa;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #6e45e2 0%, #88d3ce 100%);
        }
        .code-block {
            background-color: #2d2d2d;
            color: #f8f8f2;
            border-radius: 8px;
            position: relative;
        }
        .code-header {
            background-color: #1e1e1e;
            border-top-left-radius: 8px;
            border-top-right-radius: 8px;
            padding: 8px 16px;
            display: flex;
            align-items: center;
        }
        .code-dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
            margin-right: 8px;
        }
        .dot-red { background-color: #ff5f56; }
        .dot-yellow { background-color: #ffbd2e; }
        .dot-green { background-color: #27c93f; }
        .code-content {
            padding: 16px;
            overflow-x: auto;
        }
        .highlight {
            background-color: #ffecb3;
            padding: 2px 4px;
            border-radius: 4px;
        }
        .concept-card {
            transition: transform 0.3s ease, box-shadow 0.3s ease;
        }
        .concept-card:hover {
            transform: translateY(-5px);
            box-shadow: 0 10px 25px rgba(0, 0, 0, 0.1);
        }
        .mermaid-container {
            background-color: white;
            border-radius: 12px;
            padding: 24px;
            box-shadow: 0 4px 20px rgba(0, 0, 0, 0.08);
        }
    </style>
</head>
<body class="min-h-screen antialiased">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-4 md:px-0">
        <div class="container mx-auto max-w-6xl">
            <div class="flex flex-col md:flex-row items-center">
                <div class="md:w-1/2 mb-12 md:mb-0">
                    <h1 class="text-4xl md:text-5xl font-bold mb-6 leading-tight">正则表达式匹配算法解析</h1>
                    <p class="text-xl mb-8 opacity-90">深入理解动态规划在正则表达式匹配中的应用</p>
                    <div class="flex space-x-4">
                        <div class="bg-white bg-opacity-20 backdrop-blur-sm px-6 py-3 rounded-full font-medium flex items-center">
                            <i class="fas fa-code mr-2"></i>
                            <span>算法实现</span>
                        </div>
                        <div class="border border-white border-opacity-30 px-6 py-3 rounded-full font-medium flex items-center">
                            <i class="fas fa-project-diagram mr-2"></i>
                            <span>动态规划</span>
                        </div>
                    </div>
                </div>
                <div class="md:w-1/2">
                    <div class="bg-white bg-opacity-20 backdrop-blur-sm p-8 rounded-xl shadow-lg">
                        <div class="mermaid-container">
                            <div class="mermaid">
                                graph TD
                                    A[字符串s] --> B(初始化dp矩阵)
                                    C[模式p] --> B
                                    B --> D[处理空字符串匹配]
                                    D --> E[填充dp矩阵]
                                    E --> F[普通字符匹配]
                                    E --> G[.字符匹配]
                                    E --> H[*字符匹配]
                                    F & G & H --> I[返回最终结果dp[m][n]]
                            </div>
                        </div>
                    </div>
                </div>
            </div>
        </div>
    </section>

    <!-- Content Section -->
    <section class="py-16 px-4 md:px-0">
        <div class="container mx-auto max-w-4xl">
            <div class="bg-white rounded-xl shadow-md overflow-hidden mb-12">
                <div class="p-8">
                    <h2 class="text-3xl font-bold mb-6 text-gray-800">题目描述</h2>
                    <p class="text-lg text-gray-700 mb-4">给定一个字符串 <span class="highlight">s</span> 和一个字符模式 <span class="highlight">p</span>，实现支持 <span class="highlight">'.'</span> 和 <span class="highlight">'*'</span> 的正则表达式匹配。</p>
                    <ul class="list-disc pl-6 space-y-2 text-gray-700 mb-6">
                        <li><span class="font-medium">'.'</span> 匹配任意单个字符</li>
                        <li><span class="font-medium">'*'</span> 匹配零个或多个前面的元素</li>
                        <li>匹配应覆盖整个字符串（不是部分匹配）</li>
                    </ul>
                    <div class="bg-blue-50 border-l-4 border-blue-500 p-4 mb-6">
                        <p class="text-blue-800"><i class="fas fa-info-circle mr-2"></i>这是一个经典的动态规划问题，考察对字符串匹配算法的理解和动态规划的应用。</p>
                    </div>
                </div>
            </div>

            <!-- Algorithm Cards -->
            <div class="grid md:grid-cols-2 gap-8 mb-16">
                <div class="concept-card bg-white rounded-xl shadow-md overflow-hidden">
                    <div class="p-8">
                        <div class="flex items-center mb-4">
                            <div class="w-12 h-12 rounded-full bg-purple-100 flex items-center justify-center mr-4">
                                <i class="fas fa-sitemap text-purple-600 text-xl"></i>
                            </div>
                            <h3 class="text-2xl font-bold text-gray-800">动态规划法</h3>
                        </div>
                        <p class="text-gray-700 mb-4">定义 <code class="bg-gray-100 px-2 py-1 rounded">dp[i][j]</code> 为 <code class="bg-gray-100 px-2 py-1 rounded">s[0:i]</code> 和 <code class="bg-gray-100 px-2 py-1 rounded">p[0:j]</code> 是否匹配</p>
                        <ul class="list-disc pl-6 space-y-2 text-gray-700 mb-4">
                            <li>处理普通字符、<code>.</code> 和 <code>*</code> 的状态转移</li>
                            <li>时间复杂度: O(m×n)</li>
                            <li>空间复杂度: O(m×n)</li>
                        </ul>
                        <div class="flex items-center text-sm text-gray-500 mt-4">
                            <i class="fas fa-check-circle text-green-500 mr-2"></i>
                            <span>推荐方法，效率较高</span>
                        </div>
                    </div>
                </div>

                <div class="concept-card bg-white rounded-xl shadow-md overflow-hidden">
                    <div class="p-8">
                        <div class="flex items-center mb-4">
                            <div class="w-12 h-12 rounded-full bg-orange-100 flex items-center justify-center mr-4">
                                <i class="fas fa-network-wired text-orange-600 text-xl"></i>
                            </div>
                            <h3 class="text-2xl font-bold text-gray-800">回溯法</h3>
                        </div>
                        <p class="text-gray-700 mb-4">递归处理每种可能的匹配情况</p>
                        <ul class="list-disc pl-6 space-y-2 text-gray-700 mb-4">
                            <li>实现简单但效率较低</li>
                            <li>时间复杂度: O(2^(m+n))</li>
                            <li>空间复杂度: O(m+n)</li>
                        </ul>
                        <div class="flex items-center text-sm text-gray-500 mt-4">
                            <i class="fas fa-exclamation-triangle text-yellow-500 mr-2"></i>
                            <span>适用于小规模输入</span>
                        </div>
                    </div>
                </div>
            </div>

            <!-- Code Example -->
            <div class="mb-16">
                <h2 class="text-3xl font-bold mb-6 text-gray-800">示例代码（动态规划法）</h2>
                <div class="code-block">
                    <div class="code-header">
                        <div class="code-dot dot-red"></div>
                        <div class="code-dot dot-yellow"></div>
                        <div class="code-dot dot-green"></div>
                        <span class="text-gray-400 ml-4">python</span>
                    </div>
                    <div class="code-content">
                        <pre class="overflow-x-auto"><code class="language-python">def isMatch(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    
    # 处理空字符串匹配模式的情况
    for j in range(2, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-2]
    
    # 填充dp矩阵
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                # 两种情况：匹配0次或匹配1次及以上
                dp[i][j] = dp[i][j-2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
            elif p[j-1] == '.' or s[i-1] == p[j-1]:
                # 当前字符匹配，查看前一个状态
                dp[i][j] = dp[i-1][j-1]
    
    return dp[m][n]</code></pre>
                    </div>
                </div>
            </div>

            <!-- DP State Transition -->
            <div class="mb-16">
                <h2 class="text-3xl font-bold mb-6 text-gray-800">状态转移分析</h2>
                <div class="mermaid-container p-8">
                    <div class="mermaid">
                        stateDiagram-v2
                            [*] --> 初始化
                            初始化 --> 处理空字符串: dp[0][0]=True
                            处理空字符串 --> 填充矩阵
                            填充矩阵 --> 普通字符匹配
                            填充矩阵 --> 点号匹配
                            填充矩阵 --> 星号匹配
                            普通字符匹配 --> 检查结束: s[i]==p[j]
                            点号匹配 --> 检查结束: p[j]=='.'
                            星号匹配 --> 匹配零次: dp[i][j-2]
                            星号匹配 --> 匹配多次: dp[i-1][j]&&(s[i]==p[j-1]||p[j-1]=='.')
                            检查结束 --> 更新状态: dp[i][j]=dp[i-1][j-1]
                            匹配零次 --> 更新状态
                            匹配多次 --> 更新状态
                            更新状态 --> 填充矩阵: 继续填充
                            填充矩阵 --> 返回结果: i==m&&j==n
                    </div>
                </div>
            </div>

            <!-- Complexity Analysis -->
            <div class="bg-indigo-50 rounded-xl p-8 mb-16">
                <h2 class="text-3xl font-bold mb-6 text-gray-800">复杂度分析</h2>
                <div class="grid md:grid-cols-2 gap-8">
                    <div>
                        <h3 class="text-xl font-semibold mb-4 text-indigo-700">时间复杂度</h3>
                        <p class="text-gray-700 mb-2">动态规划法需要填充一个 (m+1)×(n+1) 的矩阵，其中 m 和 n 分别是字符串 s 和模式 p 的长度。</p>
                        <p class="text-gray-700 font-medium">O(m×n)</p>
                    </div>
                    <div>
                        <h3 class="text-xl font-semibold mb-4 text-indigo-700">空间复杂度</h3>
                        <p class="text-gray-700 mb-2">需要存储整个二维状态矩阵，可以优化为使用两个一维数组将空间复杂度降低到 O(n)。</p>
                        <p class="text-gray-700 font-medium">O(m×n) 或优化为 O(n)</p>
                    </div>
                </div>
            </div>
        </div>
    </section>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            },
            themeVariables: {
                primaryColor: '#6e45e2',
                primaryBorderColor: '#4a2d96',
                primaryTextColor: '#ffffff',
                lineColor: '#88d3ce'
            }
        });
    </script>
</body>
</html>